package nk;

/**
 * 排成一条线的纸牌博弈问题
 */
public class CardGame {

    /**
     * 输入：1 2 100 4
     * 输出：101
     */
    public static int max = 0;

    public static int cartGame(int[] arr) {
        if(arr == null || arr.length == 0) {
            return 0;
        }
        cardDFS(arr, 0, arr.length - 1, 0, true);
        return max;
    }

    public static void cardDFS(int[] arr, int l, int r, int ans, boolean flag) {
        if(!flag) {
            cardDFS(arr, l + 1, r, ans,true);
            cardDFS(arr, l , r - 1, ans,true);
            return;
        }
        if (l > r) {
            max = Math.max(max, ans);
            return;
        }
        if (l == r) {
            max = Math.max(max, ans + arr[l]);
            return;
        }
        // 只能选第一张或者最后一张
        cardDFS(arr, l + 1, r, ans + arr[l],false);
        cardDFS(arr, l, r - 1, ans + arr[r],false);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 100, 4};
//        int[] arr = {1, 2};
        System.out.println(cartGame(arr));
    }
}
